Recently, with high data rates required in mobile communication and wireless data communication, there are greater requirements on communication bandwidth efficiency or reliability. In particular, an error may be detected from digital data due to several factors in the process of transmitting and receiving the digital data, in the process of recording and reading the digital data through a storage medium, or in a process of reproducing multimedia data (i.e., audio or video data). Such an error can be corrected or reduced by using many error control schemes which have been researched up to now. Examples of the error control schemes include a Forward Error Correction (FEC) protocol and an Automatic Repeat reQuest (ARQ) protocol. A turbo code may be used in the FEC. Along with a circular tail-biting coding scheme, researches on a parallel processing technique for turbo codes have actively been conducted.
FIG. 1 is a block diagram illustrating a parallel processing method of a turbo decoder. If a full block size or an interleaver size is N, one block is divided into L sub-blocks and then parallel processing is performed. Each block has a size of M, where M=N/L. Each block receives data information from a memory under the control of individual processors 1 to L. Decoding processes are simultaneously carried out. Each processor receives the data information according to an interleaving rule determined by an interleaver or a de-interleaver.
FIG. 2 is a diagram illustrating an example of a contention occurrence in a decoding process based on parallel processing when a block consists of 4 sub-blocks. As described in FIG. 1 above, each of processors performs interleaving by reading out a data information bit from a corresponding memory according to an interleaving rule. Referring to FIG. 2, two processors (i.e., a processor 1 and a processor 2) simultaneously read out information from a first memory. Since any information can be accessed only by one processor at any one time, the information has to be accessed two times to be read out by the two processors. In this case, a contention may occur, which is indicated by 200 in FIG. 2. The occurrence of contention results in deterioration of efficiency in parallel processing. In order to avoid such a contention, various contention-free interleavers have been proposed.
An Almost Regular Permutation (ARP) interleaver is proposed by Berror. The ARP interleaver may be found in <Document 1: Designing good permutations for turbo codes: towards a single model: C. Berrou, S. Kerouedan, Y. Saouter, C. Douillard, and M. Jezequel, June 2004., in Pro. Int. Conf. Commun., p 341˜345>. In comparison with the conventional interleaver, the ARP interleaver further provides irregularity by using a relatively prime property. The ARP interleaver is defined by Equation 1 below:π(k)=(P·k+L·(α(k)·P+β(k))+γ)(mod N).  [Eqn. 1]
In Equation 1, π(k) denotes an interleaving rule of an interleaver and indicates a permutation for reading out data information from a memory by each processor. P and N are relatively prime to one other. L denotes a parallel processing order. γ denotes an initial setup value. k satisfies a relation of 0≦k≦N−1. α(k), and β(k) are positive integers having a period of L. In general, α(k) has a value between 0 and 1, and β(k) has a value between 0 to 8. The ARP interleaver is adopted by various standards such as Institute of Electrical and Electronics Engineers (IEEE) 802.16, Digital Video Broadcast-Return Channel Satellite (DVB-RCS), Digital Video Broadcast-Return Channel Terrestrial (DVB-RCT), and so forth. In addition, the ARP interleaver is proposed as an interleaver for the 3rd Generation Partnership Project 2 (3GPP2) standard.
An algebraic method is used in a Quadratic Permutation Polynomial (QPP) interleaver which may be found in <Document 2: On Maximum Contention-Free Interleavers and Permutation Polynomials Over Integer Rings: O. Y. Takeshita, March 2006., IEEE Transaction Information Theory, p 1249˜1253>. The QPP interleaver is a maximum contention-free interleaver. The QPP interleaver satisfies a contention-free condition with respect to all sub-blocks (that is, N sub-blocks each having a size of M). The QPP interleaver is defined by Equation 2 below:π(k)=f1·k+f1·k2(mod N).  [Eqn. 2]
In Equation 2, π(k) denotes an interleaving rule of an interleaver. f1 and f2 are positive integers. The aforementioned <Document 2> may be used as a reference for explaining the requirements on f1 and f2.
In addition, there is an interleaver using a Latin square matrix, wherein the interleaver determines a mixing sequence in each sub-block by using the conventional interleaver having a short length. The Latin square matrix having a size of L×L consists of L different symbols. The respective symbols are presented one by one in all rows and columns. Such a Latin square pattern can be repeated to form an M×L matrix U which represents a Latin square interleaver. The Latin square interleaver is defined by Equation 3 below:π(k)=uts·M+πT(t).  [Eqn. 3]
In Equation 3, π(k) denotes an interleaving rule of an interleaver. πT(t) denotes a conventional sub-block interleaver. uts denotes an element of a tth row and an sth column in the matrix U. M denotes a sub-block size. k satisfies a relation of k=s·M+t.
A turbo code having a parallel processing structure can be designed in a general system when parallel processing of various orders is possible for various-sized blocks supported in the system. Interleavers proposed to meet such a requirement have to undergo an optimization operation.
In case of the ARP interleaver disclosed in the aforementioned <Document 1> as the conventional technique, the following are taken into account when the optimization operation is performed. It is assumed that the initial setup value γ and the value α are determined. If k(mod L)=0, β(k) has a value of 0. Otherwise, if k(mod L)≠0, β(k) has a value between 0 to 8. In this case, the number of cases of approximately |P|·8L−1 has to be considered, where |x| denotes a cardinality of x.
In case of the QPP interleaver disclosed in the aforementioned <Document 2> as the conventional technique, there are two design methods according to a block length N. If N is divided by 4, f1 and N are positive integers and are relatively prime to one other. If N is represented as a product of prime numbers, f2 is a positive integer of which elements are the prime numbers. Therefore, the total number of cases is |f1|·|f2|.
In case of the Latin square interleaver, if L=4, a total of 576 cases exists for a 4×4 Latin square matrix. A total of 24 cases exists for a reduced Latin square matrix, in which a first row is fixed to (0,1,2,3). Among the 24 cases, only 12 cases having a good distribution are taken into account. Therefore, the number of cases for the Latin square interleaver is less than that of the interleaver disclosed in the <Document 1> or <Document 2>.
In general, the parallel processing order is 4 for a turbo code having a small or medium block size. For a turbo code having a medium or large block size, the parallel processing order is 8 or 12, which is greater than 4. Table 1 below shows the number of cases to be considered for optimization by each interleaver with respect to 3 cases.
TABLE 1N = 320, L = 4N = 640, L = 4N = 1024, L = 8ARP interleaver40960819201073741824QPP interleaver1520055360261632conventional Latin121223309006400square interleaver
In Table 1 above, the QPP interleaver considers a relatively less number of cases than the ARP interleaver but considers a significantly larger number of cases than the Latin square interleaver. In case of the Latin square interleaver, if L=4, only 12 cases are considered irrespective of a full block size. Disadvantageously, however, if L=8, the number of cases increases exponentially.